package kyssion.leetcode.num101_150;

import kyssion.leetcode.util.BuildUtil;

import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;


public class code127_单词接龙2 {
    public static void main(String[] args) {
        System.out.println(new code127_单词接龙2().ladderLength2(
                "hit", "cog", BuildUtil.createList(
                        new String[]{"hot", "dot", "dog", "lot", "log", "cog"}
                )
        ));
    }

    public boolean isChangeOne(String one, String two) {
        if (one.length() != two.length()) {
            return false;
        }
        int diff = 0;
        for (int a = 0; a < two.length(); a++) {
            if (one.charAt(a) != two.charAt(a)) {
                diff++;
            }
            if (diff > 1) {
                return false;
            }
        }
        return true;
    }

    /**
     * 使用广度搜索
     *
     * @param beginWord
     * @param endWord
     * @param wordList
     * @return
     */
    public int ladderLength2(String beginWord, String endWord, List<String> wordList) {
        int num = 0;
        if (!beginWord.equals(endWord)) {
            boolean[] useArr = new boolean[wordList.size()];
            Deque<String> que = new LinkedList<>();
            que.addFirst(beginWord);
            int beforeIndex = 1;
            while (!que.isEmpty()) {
                while (beforeIndex > 0) {
                    String item = que.removeFirst();
                    if (item.equals(endWord)) {
                        return num + 1;
                    }
                    for (int a = 0; a < wordList.size(); a++) {
                        if (!useArr[a] && isChangeOne(item, wordList.get(a))) {
                            que.addLast(wordList.get(a));
                            useArr[a] = true;
                        }
                    }
                    beforeIndex--;
                }
                num++;
                beforeIndex = que.size();
            }
            return 0;
        } else {
            return 1;
        }
    }

    /**
     * 优化的思想
     * 1. 使用hashSet 快速查找是否能匹配的想
     * 2. 双端查找如果从前向后
     * 3. 使用变化char方法的变化+
     * @param beginWord
     * @param endWord
     * @param wordList
     * @return
     */
    public int ladderLength3(String beginWord, String endWord, List<String> wordList) {
        if (wordList == null || wordList.size() == 0)
            return 0;
        //hashset的好处：去重也完成了
        //开始端
        HashSet<String> start = new HashSet<>();
        //结束端
        HashSet<String> end = new HashSet<>();
        //所有字符串的字典
        HashSet<String> dic = new HashSet<>(wordList);
        start.add(beginWord);
        end.add(endWord);
        if (!dic.contains(endWord))
            return 0;
        //经历过上面的一系列判定，到这里的时候，若是有路径，则最小是2，所以以2开始
        return bfs(start, end, dic, 2);
    }

    public int bfs(HashSet<String> begin, HashSet<String> end, HashSet<String> dic, int l) {
        //双端查找的时候，若是有任意一段出现了“断裂”，也就是说明不存在能够连上的路径，则直接返回0
        if (begin.size() == 0)
            return 0;
        if (begin.size() > end.size()) {//双端查找，为了优化时间，永远用少的去找多的，比如开始的时候塞进了1000个，而结尾只有3个，则肯定是从少的那一端开始走比较好
            return bfs(end, begin, dic, l);
        }
        //BFS的标记行为，即使用过的不重复使用
        dic.removeAll(begin);
        //收集下一层临近点
        HashSet<String> next = new HashSet<>();
        for (String s : begin) {
            char[] arr = s.toCharArray();
            for (int i = 0; i < arr.length; i++) {
                char tmp = arr[i];
                //变化
                for (char c = 'a'; c <= 'z'; c++) {
                    if (tmp == c)
                        continue;
                    arr[i] = c;
                    String nstr = new String(arr);
                    //只改变一个字母，如果字典里有，则可以转换
                    if (dic.contains(nstr)) {
                        //如果恰好end里也有，则一次转换成功
                        if (end.contains(nstr))
                            return l;
                        else
                            next.add(nstr);
                    }
                }//第一个字母全换了一遍还是没有，换下一个字母
                //复原
                arr[i] = tmp;
            }
        }
        return bfs(next, end, dic, l + 1);
    }

    /**
     * 使用深度搜索超时
     *
     * @param beginWord
     * @param endWord
     * @param wordList
     * @return
     */
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        isUse = new boolean[wordList.size()];
        int num = ans(beginWord, endWord, wordList) + 1;
        return num == Integer.MAX_VALUE ? 0 : num;
    }

    boolean[] isUse;

    public int ans(String beginWord, String endWord, List<String> wordList) {
        int min = Integer.MAX_VALUE;
        if (beginWord.equals(endWord)) {
            return 0;
        }
        for (int a = 0; a < wordList.size(); a++) {
            if (!isUse[a] && isChangeOne(beginWord, wordList.get(a))) {
                isUse[a] = true;
                int next = ans(wordList.get(a), endWord, wordList);
                min = Math.min(min, next + 1);
                isUse[a] = false;
            }
        }
        return min == Integer.MAX_VALUE ? --min : min;
    }

}
